In a LAN communication system consisting of several segments interconnected by bridges, some routing must be provided for properly guiding addressed information units such as frames through the bridges between segments. Improper routing procedures will lead to increased transmission times and will waste transmission capacity.
A general survey of routing techniques is given in an article by M. Schwadz et al. entitled "Routing Protocols", published in the book "Computer Networks and Protocols" (Ed. C. A. Sunshine), Plenum Press, New York 1989, pp.239-271. Besides various other techniques, the usage of shortest path trees for routing is described. This technique is established at the network layer. It relies on structured network addresses from which the network (segment) numbers can be inferred. Routing is done according to these network numbers. This technique is not directly applicable to bridging because MAC addresses are taken from a flat address space without any structure.
Broadcast routing also involving shortest path trees is described in an article by Y. K. Dalal et al.: "Reverse Path Forwarding of Broadcast Packets", Communications of the ACM, Vol.21, No.12, pp.1040-1048 (December 1978).
For LAN communication systems comprising several bridged segments, two bridging techniques are in widespread use today. They are called "Transparent Spanning Tree Bridging" and "Source Routing Bridging", respectively.
The Transparent Spanning Tree scheme is described e.g. in F. Backes: "Transparent Bridges for Interconnection of IEEE 802 LANs", IEEE Network, Vol.2, No.1, pp.5-9 (January 1988). The basic idea of the Transparent Spanning Tree bridging technique is to configure the bridges in such a way that the bridges and the LAN segments form a spanning tree. All bridges listen to all traffic on the LAN segments they are attached to and learn by looking at the source addresses in which direction a terminal is located. Based on this knowledge the bridges forward the frames along the spanning tree. If a destination address is unknown, the frame is broadcast to all LAN segments along the spanning tree.
This bridging technique has several deficiencies: (1) Since the LANs and bridges form a single spanning tree, in general only a subset of the available bridges can be active at any point in time. The other ones are only used as standby bridges for backup. (2) Because of the spanning tree, a route between two LAN segments may be far from optimal. Thus a frame from one LAN segment to another segment may follow a route via a large number of bridges and LAN segments although the source and destination LAN segments are directly connected by a bridge, but that bridge is not pad of the present spanning tree. (3) Transparent Spanning Tree bridges have to copy and process every frame because of the necessary learning of MAC addresses. So a bridge may be very busy without forwarding any frame. (4) Since the constantly updated table of destination addresses may become rather large, the time needed for address table lookup may become significant so that forwarding may take quite some time.
The Source Routing scheme is described in R. C. Dixon et al.: "Addressing, Bridging, and Source Routing", IEEE Network, Vol.2, No.1, pp.25-32 (January 1988). The basic idea of the Source Routing bridging technique is to have routing information included in every frame by the source terminals. The information describes the whole path the frame has to take starling from the source LAN segment through all intermediate bridges and LAN segments to the destination LAN segment. The bridges thus simply forward the frames based on this routing information. Before the routing information can be used, discovery frames from the source to the destination terminal are sent throughout the network with the bridges recording the routes in the discovery frames and discarding circling frames. The destination terminal replies to these discovery frames so that the source terminal also learns the route. One of several routes may be selected by either the source terminal or the destination terminal.
This bridging scheme also has some shortcomings: (1) There is an upper bound for the routing information carried inside the MAC frames. If this upper bound is low, routing is restricted to a small number of hops. If it is high, the frame overhead is becoming significant in length. (2) It is not possible to change the routing behaviour in a bridged LAN in a way transparent to the terminals, because a source route exactly prescribes the path through the network that the frame has to follow. Thus there is no way to adapt the network to changing traffic loads without the terminals being involved.